package LeetCodeHot100TopInterview;

public class Q105_BuildTreeFromPreAndOrder {
    //从前序和中序构建二叉树
    //同剑指offer Q007
//给前序和中序 给后序树
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 0 || preorder.length != inorder.length){
            return null;
        }

        return process(preorder,inorder,0, preorder.length - 1, 0, inorder.length - 1);

    }

    public static TreeNode process(int[] pre, int[] in,
                                   int preLeft, int preRight,
                                   int inLeft, int inRight){

        //base case
        if (preLeft > preRight || preLeft == -1){
            return null;
        }



        //前序第一个就是根 「 根 」 「左子树... 」 「右子树...」
        //定位中序的根节点 [左子树...] [根] [右子树...]
        int inRoot = pre[preLeft];

        //计算前序的范围
        //1.计算中序列中左子树内的数量，题目表示无重复
        //该数量在前序列中也同样适用
        int count = 0;
        //根节点下标
        int i = 0;
        for (i = inLeft; i < inRight; i++) {
            if (inRoot != in[i]){
                count ++;
            }else {
                break;
            }
        }
        //
        TreeNode root = new TreeNode(inRoot);
        //left

        //左子树节点数
        int countLeft = count;
        //右子树节点数
        int countRight = preRight - preLeft + 1 - 1 - count;

        int temp = preLeft;
        preLeft = countLeft != 0 ? preLeft + 1 : -1;
        preRight = preLeft != -1 ? temp + countLeft : -1;
        inLeft = i - countLeft;
        inRight = i - 1;
        root.left = process(pre,in, preLeft, preRight, inLeft, inRight);

        //right
        preLeft = countRight != 0 ? temp + countLeft + 1 : -1;
        preRight = preLeft != -1 ? temp + countLeft  + countRight : -1;
        inLeft = i + 1;
        inRight = i  + countRight;
        root.right = process(pre,in, preLeft, preRight, inLeft, inRight);;

        return root;
    }


}
